In general, routing can be defined as the act of moving information from a source. to a destination via one or more intermediate nodes in a communication network.
When routing is applied in a wireless network, such a network is often referred to as a multihop network. In a multihop network, nodes out of reach from each other may benefit from intermediately located nodes that can forward their messages from the source towards the destination. Traditionally, multihop networks have often been associated with so called ad hoc networks where nodes are mostly mobile and no central coordinating infrastructure exists. However, the idea of multihop networking can also be applied when nodes are fixed. In addition, one can also envision central coordination, in particular when nodes are fixed and channels are robust. One may also envision hybrid networks involving wired links in addition to wireless links in multihop networks. A common type of multihop network is based on so called store and forward, where the entire packet is received prior to forwarding.
Routing generally involves two basic tasks: determining suitable routing paths and transporting information through the network. In the context of the routing process, the first of these tasks is normally referred to as route determination and the latter of these tasks is often referred to as packet forwarding.
For route determination, a common approach is to span a so-called routing tree. FIG. 1A illustrates an example of such a routing tree, here rooted at a given destination node. The routing tree is normally calculated based on a shortest path algorithm, implying that the determined shortest paths from the various nodes in the tree to the destination node are so-called “least cost paths”. In practice, the tree is continuously built and updated to manage mobility and changing link conditions.
When a particular node in the tree wants to send a packet in the subsequent packet forwarding process, the node is considered a source node, and the packet follows the determined routing path from the source to the destination, as illustrated in FIG. 1B. Different nodes may send packets to the same destination over time, hence different nodes will act as source nodes and send along their respective shortest path. In addition, as multiple destinations may exist, multiple trees may be generated, each rooted at a corresponding destination.
Packet forwarding is normally relatively straightforward, whereas path or route determination can be very complex.
Routing protocols generally use so-called routing metrics as a base for evaluating which path or route that will be the best for a given packet and thereby determining the optimal path to the destination. In the prior art, many different metrics have been used by the routing algorithms to determine the best, or at least a suitable route.
A classical wireline hop metric is unsuitable in a wireless environment, basically since it does not reflect the link quality dependency with respect to distance. Also, transmit power is an important factor in affecting the link quality.
An example of a wireline metric of less use in wireless situations, yet frequently encountered, is a simple hop count metric, where the link cost ΔCij from node vi to vj is defined as ΔCij=1.
Another metric that has been suggested in the research literature is based on the physical distance between two nodes, e.g. ΔCij=Distanceij.
A better example suited for a radio environment is to use the average link gain Gij and define link cost as the inverse of the average link gain, i.e. ΔCij=Gij−1. This metric provides large receiver SNR (Signal-to-Noise Ratio) values (with fixed power), and minimum power routes (with power control). This is not a bad metric, but it may lead to a situation where packets will experience long delays (mainly since it does not reflect the capacity of a link appropriately).
Hence an even better link metric example is to use the estimated average link rate and define link cost as the inverse of the average link rate, i.e. ΔCij=1/ rij, assuming rate adaptation capabilities. This metric can be seen in two ways. First, for a fixed sized packet, it strives to offer minimum delay paths (assuming that the queuing delay in the network is negligible). However, in the context of a multihop scheme with a fixed sized data phase (with varying number of packets in a data phase depending on rate adaptation) it offers the least time resource utilization along a path. The average rate based link metric can be estimated by the classical Shannon capacity:
                                                        r              _                        ij                    =                      B            ·                          E              (                                                log                  2                                (                                  1                  +                                                                                    G                        ij                                            ⁢                                              P                        i                                                                                    σ                      N                      2                                                                      )                            )                                      ,                            (        1        )            where B is the bandwidth (may be neglected if only one common bandwidth is used in the whole system), E { . . . } is the expectation value, Pi is the transmit power of node vi (which may be fixed or determined by some other mechanism), σN2 is the noise level (at node vj). The term, σN2 could potentially also include average interference, then modeled as complex Gaussian noise, apart from receiver noise.
Using the Shannon capacity for the inverse gain metric case described above, it is seen that it corresponds to minimum power routing with a given target link rate rij(Target). The minimum power is then determined as:
                              P          i                =                              (                                          2                                                                            r                      _                                        ij                                          (                      Target                      )                                                        B                                            -              1                        )                    ⁢                                    σ              N              2                                      G              ij                                                          (        2        )            Reference [1] describes the use of link transmit power as a reasonable cost metric to minimize the cumulative transmit power used over an entire path. This is good for battery consumption and also reduces the interference level in the system, leaving space for new connections and thus allowing operation at higher network load.
As indicated, it is possible to include interference in the metric. Interference-based type of metrics include Least Interference Routing (LIR), where the idea is to use a route that causes the least destructive interference, and Least Resistance Routing (LRR), where the idea is to use the route encountering the least interference.
It is also possible to include traffic load in the metric. However, including such traffic aspects in the metric (e.g. incorporating aspects of traffic load and medium access rules) is not straightforward, as one then also needs to consider stability issues.
It is evident that the routing metric has a substantial effect on route determination, and therefore it is of significant importance to provide enhanced metrics for determining suitable routes. Improved route selection then naturally leads to improved routing with higher throughput and reduced delay in the networks.